package cn.edu.jxau.test;

/**
 * http://web.jobbole.com/86192/
 * https://www.zhihu.com/question/36132386
 * http://blog.csdn.net/yefengzhichen/article/details/52372407
 * http://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html
 * http://blog.csdn.net/luckyxiaoqiang/article/details/8937978
 
 * @author 付大石
 */
public class BinarySearch {

    public static void main(String[] args) {

        int[] arr = { 2, 3, 5, 7, 11, 13, 17 };
        System.out.println(getLastIndex(arr,1));
    }

    private static int upperBound(int arr[], int target) {
        
        int low = 0;
        int high = arr.length -1;
        int mid = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            if (arr[mid] > target)
                high = mid-1;
            else
                low = mid + 1;
        }
        System.out.println(low+"    "+mid);
        return mid;
    }

    // ---------------------------
    // 最原始的二分搜索
    // ---------------------------
//    private static int search(int[] arr, int key) {
//
//        int low = 0;
//        int high = arr.length - 1;
//        while (low <= high) {
//            int mid = low + (high - low) / 2;
//            if (arr[mid] == key) {
//                return mid;
//            } else if (arr[mid] < key) {
//                low = mid + 1;
//            } else {
//                high = mid - 1;
//            }
//        }
//        return -1;
//    }

    // ---------------------------
    // 递归的二分搜索
    // ---------------------------
//    private static int search(int[] arr, int key) {
//        return search(arr, key, 0, arr.length - 1);
//    }
//
//    private static int search(int[] arr, int key, int low, int high) {
//
//        if (low > high) {
//            return -1;
//        }
//        int mid = low + (high - low) / 2;
//        if (arr[mid] == key) {
//            return mid;
//        } else if (arr[mid] < key) {
//            return search(arr, key, mid + 1, high);
//        } else {
//            return search(arr, key, low, mid - 1);
//        }
//    }

    // --------------------------------------------------
    // 利用二分搜索的思想，获取数组中小于key的元素个数
    // --------------------------------------------------
//    private static int getLessThan(int[] arr, int key) {
//
//        int low = 0;
//        int high = arr.length - 1;
//        while (low <= high) {
//            int mid = low + (high - low) / 2;
//            if (arr[mid] == key) {
//                return mid;
//            } else if (arr[mid] < key) {
//                low = mid + 1;
//            } else {
//                high = mid - 1;
//            }
//        }
//        return low;
//    }

    // ----------------------------------------------------------
    // 利用二分搜索的思想，获取数组中key第一次出现的位置，不存在则返回-1
    // ----------------------------------------------------------
//    private static int getFirstIndex(int[] arr, int key) {
//
//        int low = 0;
//        int high = arr.length - 1;
//        int result = -1;
//        while (low <= high) {
//            int mid = low + ((high - low) >> 1);
//            if (arr[mid] < key) {
//                low = mid + 1;
//            } else if (arr[mid] > key) {
//                high = mid - 1;
//            } else {
//                result = mid;
//                high = mid - 1;
//            }
//        }
//        return result;
//    }

    private static int getFirstIndex(int[] arr, int key) {

        int low = 0;
        int high = arr.length-1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] >= key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return (low<arr.length && arr[low] == key) ? low : -1;
    }

    // ----------------------------------------------------------
    // 利用二分搜索的思想，获取数组中key最后一次出现的位置，不存在则返回-1
    // ----------------------------------------------------------
//    private static int getLastIndex(int[] arr, int key) {
//
//        int low = 0;
//        int high = arr.length - 1;
//        int result = -1;
//        while (low <= high) {
//            int mid = low + ((high - low) >> 1);
//            if (arr[mid] < key) {
//                low = mid + 1;
//            } else if (arr[mid] > key) {
//                high = mid - 1;
//            } else {
//                result = mid;
//                low = mid + 1;
//            }
//        }
//        return result;
//    }

    private static int getLastIndex(int[] arr, int key) {

        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] <= key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return (high >=0 && arr[high] == key) ? high : -1;
    }

    // --------------------------------------------------------------------------------------
    // 利用二分搜索的思想，进行ceiling操作，获取有序数组中大于等于key的元素的最小的下标
    // --------------------------------------------------------------------------------------
//    public static int ceiling(int arr[], int key) {
//
//        int low = 0, high = arr.length - 1;
//        int result = -1;
//        while (low <= high) {
//            int mid = low + ((high - low) >> 1);
//            if (arr[mid] >= key) {
//                result = mid;
//                high = mid - 1;
//            } else {
//                low = mid + 1;
//            }
//        }
//        return result;
//    }

    public static int ceiling(int arr[], int key) {

        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] >= key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    // --------------------------------------------------------------------------------------
    // 利用二分搜索的思想，进行floor操作，获取有序数组中小于等于key的元素的最大的下标
    // --------------------------------------------------------------------------------------
//    public static int floor(int arr[], int key) {
//
//        int low = 0, high = arr.length - 1;
//        int result = -1;
//        while (low <= high) {
//            int mid = low + ((high - low) >> 1);
//            if (arr[mid] <= key) {
//                result = mid;
//                low = mid + 1;
//            } else {
//                high = mid - 1;
//            }
//        }
//        return result;
//    }

    public static int floor(int arr[], int key) {

        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] <= key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return high;
    }

    // -------------------------
    // 面向链表的二分查找
    // -------------------------
    
    //--------------------------
    // 轮转后的有序数组上应用二分查找
    //--------------------------
    
    //---------------------------
    // 查找数组中某个数的出现次数
    //---------------------------
    
}
